package features.advance.leetcode.string.hard;


import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Stack;

/**
 *  32. 最长有效括号
 *
 *  难度：困难
 *
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "(()"
 * 输出：2
 * 解释：最长有效括号子串是 "()"
 * 示例 2：
 *
 * 输入：s = ")()())"
 * 输出：4
 * 解释：最长有效括号子串是 "()()"
 * 示例 3：
 *
 * 输入：s = ""
 * 输出：0
 *
 *
 * 提示：
 *
 * 0 <= s.length <= 3 * 104
 * s[i] 为 '(' 或 ')'
 *
 * @author LIN
 * @date 2021-07-27
 */
public class Solution32 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
        };
        String s = ")(())))(())())";
        int res = solution.longestValidParentheses(s);
        System.out.println(res);

    }

    static class Solution {
        public int longestValidParentheses(String s) {
            if(s == null || s.length()==0){
                return 0;
            }

            List<Integer> list = new ArrayList<>();

            Stack<pair> stack = new Stack<>();
            for(int i=0;i<s.length();i++){
                if(stack.isEmpty()){
                    stack.add(new pair(s.charAt(i),i));
                }else{
                    if(s.charAt(i) == parseChar(stack.peek().c)){
                        pair p = stack.pop();
                        list.add(p.index);
                        list.add(i);
                        System.out.println(p.index);
                        System.out.println(i);
                    }else {
                        stack.add(new pair(s.charAt(i),i));
                    }
                }
            }
            if(list.isEmpty()){
                return 0;
            }
            list.sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1-o2;
                }
            });
            System.out.println(list);
            Integer integer1 = list.get(0);
            int tmp = 1;
            int res = 0;

            for (int i = 1; i < list.size(); i++) {
                Integer integer = list.get(i);

                if(integer - integer1 == 1){
                    tmp++;
                    res = Math.max(res,tmp);
                }else {
                    res = Math.max(res,tmp);
                    tmp = 1;
                }
                integer1 = integer;
            }
            return res;
        }


        public char parseChar(char a){
            switch (a){
                case '(':
                    return ')';
                case '[':
                    return ']';
                case '{':
                    return '}';
                default:
                    return '0';

            }

        }

        static class pair{
            public Character c;
            public Integer index;

            public pair(Character c, Integer index) {
                this.c = c;
                this.index = index;
            }
        }
    }
}
